938C - Constructing Tests - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

#define PI acos(-1.0)
typedef long long ll; 

const int maxx = 1e9;

int solve(ll n,ll x){
	if(n*n <= x) return -1;
	ll i,j,k1,k2,low,high,mid;
	i = n*n;
	low = 2,high = n;
	while(low<=high){
		mid = (low+high)/2;
		j = n/mid;
		k1 = i - j*j;
		//k2 = i - (mid*mid);
		if(k1 == x) return mid;
		//else if(k2 == x) return j;
		else if(k1 < x){
			low = mid+1;
		}
		else if(k1 > x){
			high = mid-1;
		}
	}
	return -1;
}

int main(){
	ll t,i,j,k,x,n,m;
	cin >> t;
	while(t--){
		scanf("%lld",&x);
		if(x == 0){
			n = m = 1;
		}
		else{
			for(i=sqrtl(x);i<1e5;i++){
				if((i*i - (i/2)*(i/2)) > maxx){
					n = m = -1;
					break;
				}
				m = solve(i,x);
				if(m != -1){
					n = i;
					break;
				}
			}
		}
		if(n == -1){
			printf("-1\n");
		}
		else{
			printf("%lld %lld\n",n,m);
		}
	}
return 0;		
}